It is often the case that, in order to increase the speed of database search with specified conditions for multiple attributes, an index is generated on the basis of the multiple attributes. The following two techniques are known as methods of generating an index based on multiple attributes.
The first technique is a method called compound index (refer to NPL 1, below). In the compound index, priorities are assigned to multiple attributes desired to be used for an index, and the attributes are sorted in order of priority and stored. Specifically, assume a case where the attribute value of an attribute A is represented by a bit string “A1A2A3A4” and the attribute value of an attribute B is represented by a bit string “B1B2B3B4”. In this case, an index key “A1A2A3A4|B1B2B3B4”, which is formed by connecting the individual attribute values with a separation mark “|”, is sorted, and the sorting result is stored. Since attribute values are sorted in order of priority, it is possible to generate a compound index even when the attributes have attribute values that are different in bit length. Moreover, when attribute values are discrete values, the efficiency of query processing with a specified matching condition for the attribute values can be increased.
The second technique is a method called UB-Tree (refer to NPL 2, below). In the UB-Tree, an index key is generated by targeting multiple attributes desired to be used for an index, by alternately arranging the bits of the attribute values on a bit-by-bit basis, and the index key is sorted and stored. Specifically, assume a case where the attribute value of an attribute A is represented by a bit string “A1A2A3A4” and the attribute value of an attribute B is represented by a bit string “B1B2B3B4”. In this case, the bits of the attribute values are alternately arranged on a bit-by-bit basis. Through this operation, the UB-Tree generates an index key “A1B1A2B2A3B3A4B4” and stores, as an index, the result obtained by sorting the index key. According to the UB-Tree, in which the bits of attribute values are alternately arranged on a bit-by-bit basis, it is relatively easy to obtain continuity for the attributes, so that efficiency in range search is likely to be higher than that in the above-described compound index. The index key generating technique employed in the UB-Tree is called bit-interleaving or Z-ordering, for example. In the following description, a method of generating an index key by alternately arranging the bits of attribute values on a bit-by-bit basis is referred to representatively as bit-interleaving.
The UB-Tree, which alternately arranges the bits of attribute values on a bit-by-bit basis, is based on the assumption that the bit lengths of attribute values are the same. Zero padding is often employed in order to have the same bit length for all pieces of data. However, zero padding increases index keys in size.
To address this problem, in the technique proposed in NPL 2, the order of arranging bits is limited to the descending order of bit length of attribute values, and an index key is generated by skipping, when the bit length of an attribute value exceeds a certain length, the attribute. In other words, the proposed technique addresses the problem of the difference in bit length among attribute values by limiting the generation method to one in which an index key is generated by alternately arranging the bits of the bit strings of attribute values in a left-justified manner.